package leetcode.tree;

/**
 * 返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
 *
 * (回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）
 *
 *  
 *
 * 示例：
 *
 * 输入：[8,5,1,7,10,12]
 * 输出：[8,5,10,1,7,null,12]
 *
 *  
 *
 * 提示：
 *
 * 1 <= preorder.length <= 100
 * 先序 preorder 中的值是不同的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal
 */
public class 先序遍历构造二叉树 {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    class Solution {
        public TreeNode bstFromPreorder(int[] preorder) {
            if (preorder == null){
                return null;
            }
            TreeNode root = new TreeNode(preorder[0]);
            for (int i = 1; i < preorder.length; i++){
                TreeNode t = new TreeNode(preorder[i]);
                TreeNode next;
                TreeNode parent = root;
                if (t.val < root.val){
                    next = root.left;
                }else {
                    next = root.right;
                }
                while (next != null){
                    parent = next;
                    if (t.val < next.val){
                        next = next.left;
                    }else {
                        next = next.right;
                    }
                }
                if (t.val < parent.val){
                    parent.left = t;
                }else {
                    parent.right= t;
                }
            }
            return root;
        }
    }
    public TreeNode bstFromPreorder(int[] preorder) {
        return helper(preorder,0,preorder.length-1);
    }
    private TreeNode helper(int []preorder,int left,int right){
        if (left>right)
            return null;
        int index=-1;//用来找比根节点大的第一个点，也就是右子节点的开始
        for (int i=left;i<=right;i++){
            if (preorder[i]>preorder[left]){
                index=i;
                break;
            }
        }
        TreeNode node=new TreeNode(preorder[left]);//创建当前深度的根节点
        if (index!=left) {//满足则说明左子树不为空
            if (index!=-1)
                node.left = helper(preorder, left + 1, index - 1);
            else
                node.left = helper(preorder, left + 1, right);
        }
        if (index!=-1)//满足则说明右子树不为空
            node.right = helper(preorder, index, right);
        return node;
    }

}
